package arithmetic.array;

/**
 * 有序数组拆分两部分，前后置换组成新数组，查值
 */
public class RBinarySearch {

    /**
     * @param arr 数组
     * @param x   要查得值
     * @return
     */
    public static int BSearch(int[] arr, int x) {
        int low = 0, high = arr.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] == x) {
                return mid;
            }
            if (arr[mid] > arr[high]) {
                if (arr[low] <= x && x < arr[mid]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            } else {
                if (arr[mid] < x && x <= arr[high]) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
        }
        return -1;
    }


    public static void main(String[] args) {
        int[] arr = {4, 5, 7, 9, 1, 2, 3};
        System.out.println(BSearch(arr, 3));
    }
}
